package all;

import leetcodeHis.ListNode;
import test0ne.TreeNode;

import java.util.*;

/**
 * @author by zhangleishuidihuzhu.com
 * @Date 2023/2/28 20:04
 * @DESC 这个是全部刷
 */
public class TestAll {

    public static void main(String[] args) {
        TestAll t = new TestAll();
//        System.out.println(t.myAtoi("20000000000000000000"));

//        TreeNode treeNode = new TreeNode(10);
//        treeNode.left = new TreeNode(5);
//        treeNode.left.left = new TreeNode(3);
////        treeNode.left.left.left = new TreeNode(3);
////        treeNode.left.left.right = new TreeNode(-2);
//        treeNode.left.right = new TreeNode(2);
////        treeNode.left.right.right = new TreeNode(1);
//        treeNode.right = new TreeNode(-3);
////        treeNode.right.left = new TreeNode(6);
//        treeNode.right.right = new TreeNode(11);
//        System.out.println(t.pathSum(treeNode, 10));

//        System.out.println(t.mySqrt(2));
//        System.out.println(t.mySqrt(4));
//        System.out.println(t.mySqrt(5));
//        [[1,3],[2,6],[8,10],[15,18]]
        List<List<Integer>> list = t.combinationSum2(new int[]{10,1,2,7,6,1,5}, 8);
//        System.out.println(list.stream());
//        System.out.println();
    }


    /**
     * 82 含有重复元素的组合
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> list = new LinkedList<>();
        combinationSum21(candidates, 0, target, list, result);
        return result;
    }

    private void combinationSum21(int[] candidates, int index, int target, LinkedList<Integer> list, List<List<Integer>> result) {
        if(target<=0 || index == candidates.length) {
            if(target == 0 ) {
                List<Integer> list1 = new ArrayList<>(list);
                list1.sort(Comparator.comparingInt(o -> o));
                if(!result.contains(list1)) {
                    result.add(list1);
                    list.forEach(System.out::print);
                    System.out.println();
                }
            }
            return;
        }

        combinationSum21(candidates, index+1, target, list, result);

        list.add(candidates[index]);
        combinationSum21(candidates, index+1, target-candidates[index], list, result);
        list.removeLast();
    }

    /**
     * 81 允许重复选择的元素组合
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> list = new LinkedList<>();
        combinationSum22(candidates, 0, target, list, result);
        return result;
    }

    private void combinationSum22(int[] candidates, int index, int target, LinkedList<Integer> list, List<List<Integer>> result) {
        if(target <= 0 ) {
            if (target == 0 ) {
                result.add(new ArrayList<>(list));
            }
            return;
        }
        if(index==candidates.length) {
            return;
        }

        //不放当前，直接后移
        combinationSum22(candidates, index+1, target, list, result);

        //放当前，下标不移动
        list.add(candidates[index]);
        combinationSum22(candidates, index, target-candidates[index], list, result);
        list.removeLast();
    }


    /**
     * 80 含有k个元素的组合
     * @param n
     * @param k
     * @return  给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> list = new LinkedList<>();
        combine2(n, k, list, result);
        return result;
    }

    private void combine2(int n, int k, LinkedList<Integer> list, List<List<Integer>> result) {
        if(k == 0) {
            result.add(new ArrayList<>(list));
            return;
        }
        if(n < 1) {
            return;
        }

        //1、放  不放两种，  放 k-1 不放k不变
        list.add(n);
        combine2(n-1, k-1, list, result);
        list.removeLast();

        combine2(n-1, k, list, result);
    }





    /**
     * 79 所有子集
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> list = new LinkedList<>();
        subsets2(nums, 0, list, result);
        return result;
    }

    private void subsets2(int[] nums, int i, LinkedList<Integer> list, List<List<Integer>> result) {
        if(i== nums.length) {
            result.add(new LinkedList<>(list));
            result.get(result.size()-1).forEach(System.out::print);
            System.out.println();
            return;
        }

        int index = i +1;
        subsets2(nums, index, list, result);

        list.add(nums[i]);
        subsets2(nums, index, list, result);
        list.removeLast();
    }

    /**
     * 77 链表排序
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

//        ListNode pre1 = dummy;
//        ListNode cur = head;
//        while (cur != null) {
//            ListNode next = cur.next;
//            while (next != null) {
//                ListNode pre2 = cur;
//
//                if(cur.val>next.val) {
//                    ListNode next1 = cur.next;
//
//                    ListNode
//                }
//            }
//
//        }
        return null;
    }


    /**
     * 76 数组中的第k大数组
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int num : nums) {
            queue.add(num);
            if(queue.size()>k) {
                queue.poll();
            }
        }
        return queue.peek();
    }

    /**
     * 75 数组的相对排序  将arr1 按 arr2排序
     * @param arr1
     * @param arr2
     * @return
     */
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr2.length; i++) {
            map.put(arr2[i], i);
        }

        List<Integer> last = new ArrayList<>();
        List<Integer> begin = new ArrayList<>();
        for (int i = 0; i < arr1.length; i++) {
            if(map.get(arr1[i]) == null) {
                last.add(arr1[i]);
            }else {
                begin.add(arr1[i]);
            }
        }
        last.sort(Comparator.comparing(Integer::intValue));
        begin.sort(Comparator.comparingInt(map::get));
        begin.addAll(last);
        int[] result =new int[begin.size()];
        for (int i = 0; i < begin.size(); i++) {
            result[i] = begin.get(i);
        }
        return result;
    }


    /**
     * 74 合并区间
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            for (int j = i+1; j < intervals.length; j++) {
                int fir = intervals[i][0];
                int sec = intervals[j][0];
                if(fir>sec) {
                    int[] temp = intervals[i];
                    intervals[i] = intervals[j];
                    intervals[j] = temp;
                }
            }
        }

        for (int i = 0; i < intervals.length;i++) {
            int[] one = new int[]{0,0};
            int[] cur = intervals[i];
            one[0] = cur[0];
            one[1] = cur[1];

            int before = one[1];
            int index = i+1;
            while (index<=intervals.length) {
                if(index == intervals.length) {
                    i = index;
                    break;
                }
                int[] sec = intervals[index];

                int begin = sec[0];
                int end = sec[1];
                if(before<begin) {
                    i = index-1;
                    break;
                }else if(before<=end){
                    before = end;
                    one[1] = end;
                }
                index++;
            }
            list.add(one);
        }

        int[][] result = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }


    /**
     *
     * [30,11,23,4,20]
     * 6
     * 73 狒狒吃香蕉
     * @param piles
     * @param h
     * @return
     */
    public int minEatingSpeed(int[] piles, int h) {
        Arrays.sort(piles);
        int slow = 1;
        int fast = piles[piles.length-1];

        while (slow<=fast) {
            int mid = slow + (fast-slow)/2;

            int hours = getRate(piles, mid);
            if(hours==h) {
                if(getRate(piles, mid-1) != h) {
                    return mid;
                }
                fast = mid-1;
            }else if(hours>h) {
                slow = mid+1;
            }else {
                fast = mid - 1;
            }
        }
        return slow;
    }

    private int getRate(int[] piles, int mid) {
        int result = 0;
        for (int pile : piles) {
            if(pile % mid == 0) {
                result += pile/mid;
                continue;
            }
            result += pile/mid+1;
        }
        return result;
    }

    /**
     * 72 开方 只输出整数部分， 输出正数
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        if(x<=1) {return x;}
        int left = 0;
        int right = x;
        while (left<=right) {
            int mid = left + (right-left)/2;
            if( mid == x/mid) {
                return mid;
            }

            if(mid>x/mid) {
                right = mid-1;
            }else {
                if((mid+1) >x /(mid+1)) {
                    return mid;
                }
                left = mid+1;
            }
        }
        return left;
    }

    /**
     * 69 山峰数组的顶部
     * @param arr
     * @return  3 5 3 2 0
     */
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;

        while (left<=right) {
            int mid = left + (right - left) /2;

            int cur = arr[mid];

            if(mid>0 && cur<arr[mid-1]) {
                right = mid-1;
            }else {
                if(cur>arr[mid+1]) {
                    return mid;
                }
                left = mid+1;
            }
        }
        return 0;
    }


    /**
     * 71
     * @param w
     */
    private int[] sum;

    private Random random;

    public void Solution(int[] w) {
        sum = new int[w.length];
        random = new Random();
        int s = 0;
        for (int i = 0; i < w.length; i++) {
            int cur = w[0];
            s += w[i];
            sum[i] = s;
        }

    }

    public int pickIndex() {
        int target = random.nextInt(sum[sum.length-1]);
        int l = 0;
        int r = sum.length-1;
        while (l<=r) {
            int mid = l + (r - l) /2;

            int midValue = sum[mid];
            if(target <= midValue) {
                if(mid-1>=0 && target>sum[mid-1]) {
                    return mid;
                }
                 r = mid-1;
            }else {
                if(mid + 1<sum.length && target<=sum[mid+1]) {
                    return mid+1;
                }
                l = mid+1;
            }
        }
        return l;
    }


    /**
     * 70 排序数组中只出现一次的数字
     * @param nums
     * @return
     */
    public int singleNonDuplicate(int[] nums) {
        //1、异或运算
//        int result = nums[0];
//        for (int i = 1; i < nums.length; i++) {
//            int cur = nums[i];
//            result ^= cur;
//        }
//        return result;

        //2、二分查找
        int left = 0;
        int right = nums.length-1;
        while (left <= right) {
            int mid = left + (right-left)/2;

            if(mid+1<nums.length && nums[mid+1] == nums[mid]) {
                if (mid % 2 == 0) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }else if(mid - 1 >=0 && nums[mid-1] == nums[mid]) {
                if (mid % 2 == 0) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }else {
                return nums[mid];
            }
        }
        return left;
    }


    /**
     * 68 查找插入位置
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while (left<=right) {
            int mid = left + (right-left) / 2;

            int cur = nums[mid];
            if(cur == target) {
                return mid;
            }else if(cur > target) {
                if(mid == 0 ) {
                    return 0;
                }
                if(nums[mid-1] < target) {
                    return mid ;
                }
                right = mid-1;
            }else {
                left = mid+1;
            }
        }
        return left;
    }


    /**
     * 出现频率最高的k个数字
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            if(map.get(cur) == null) {
                map.put(cur, 1);
            }else {
                map.put(cur, map.get(cur)+1);
            }
        }

        PriorityQueue<Map.Entry<Integer, Integer>> p = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            p.add(e);
            if(p.size()>k) {
                p.poll();
            }
        }
        int[] result = new int[k];
        int index = 0;
        while (!p.isEmpty()) {
            result[index++] = p.poll().getKey();
        }
        return result;
    }



    private PriorityQueue<Integer> p;

    private Integer cap;

    public void KthLargest(int k, int[] nums) {
        cap = k;
        p = new PriorityQueue<>((o1,o2) -> o2.intValue() - o1.intValue());
        for (int num : nums) {
            add(num);
        }

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1,o2) -> o2 - o1);
    }

    public int add(int val) {
        p.add(val);

        if(p.size() > cap) {
            p.poll();
        }
        return p.peek();
    }


    /**
     * 57 值和下标都在给定范围内   值小于 t， 下标 < k
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        //使用一个map 存储，值， 下标
        //最笨的方法，遍历两次
        for (int i = 0; i < nums.length-1; i++) {
            long first = nums[i];
            for (int j = 1; j < k+1 && i+j<nums.length; j++) {
                long second = nums[i+j];

                if(Math.abs(first - second) <= t) {
                    return true;
                }

            }
        }
        return false;



//        Map<Integer, Integer> map = new HashMap<>();
//        for (int i = 0; i < nums.length; i++) {
//            int cur = nums[i];
//            if()
//        }
    }


    /**
     * 56 二叉搜索树中的两个节点之和
     * @param root
     * @param k
     * @return
     */
    public boolean findTarget2(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        return findTargetChild(root, k, set);
    }

    private boolean findTargetChild(TreeNode root, int k, Set<Integer> set) {
        if (root != null) {
            int cur = root.val;
            if(set.contains(k-cur)) {
                return true;
            }
            set.add(cur);
        }

        return root != null && (findTargetChild(root.left, k, set) || findTargetChild(root.right, k, set));
    }


    private Stack<TreeNode> s = new Stack<>();

    public TreeNode convertBST(TreeNode root) {
        inorderBST(root);

        int value = 0;
        while (!s.isEmpty()) {
            TreeNode cur = s.pop();
            cur.val += value;
            value = cur.val;
        }

        return root;
    }

    private void inorderBST(TreeNode root) {
        if(root==null) {
            return;
        }
        increasingBST(root.left);
        s.add(root);
        increasingBST(root.right);
    }

    private TreeNode convertBSTRight(TreeNode root) {
        if(root == null) {
            return null;
        }
        TreeNode right = convertBSTRight(root.right);

        return null;

    }

    private TreeNode convertBSTChild(TreeNode left, TreeNode root) {
        if(left == null) {
            return null;
        }
//        if(left.)
        left.val = left.val+root.val;
        return left;
    }

    /**
     * 12
     * @param nums
     * @return
     */
    public int pivotIndex(int[] nums) {

        int sum = 0;
        int[] arr = new int[nums.length];
        for(int i = 0; i<nums.length;i++) {
            sum += nums[i];
            arr[i] = sum;
        }

        int leftSum = 0;
        for(int i = 0; i<nums.length;i++) {
            if(i > 0) {
                leftSum = arr[i-1];
            }
            int rightSum = arr[nums.length-1] - arr[i];
            if(leftSum == rightSum) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 122 股票买卖的最佳时机 II
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
//        return maxProfixStep(prices, 0);
        //单调栈
        if(prices.length <= 1) {
            return 0;
        }
        Stack<Integer> s = new Stack<>();
        s.add(prices[prices.length-1]);
        int result = 0;

        int min = -1;
        int max = s.peek();
        for (int index = prices.length-2; index >= 0; index--) {
            int cur = prices[index];
            int peek = s.peek();
            if(cur > peek) {
                //清空并计算
                while (!s.isEmpty()) {
                    s.pop();
                }
                if(min != -1 && max != -1) {
                    result += (max-min);
                }
                min = -1;
                max = -1;
            }
            s.add(cur);
            if(max == -1) {
                max = cur;
            }else {
                min = cur;
            }
        }

        if(min != -1 && max != -1) {
            result += (max-min);
        }

        return result;
    }

    private int maxProfixStep(int[] prices, int index) {
        int min = prices[index];
        int max = prices[index];
        int curSum = 0;

        for (int i = index; i < prices.length; i++) {
            int cur = prices[i];
            index = i;

            if(cur<=min && cur>max) {
                min = cur;
                max = cur;
            }else {
                if(cur>=max) {
                    max = cur;
                    curSum = Math.max(curSum, max-min);
                }else {
                    break;
                }
            }
        }
        return index<prices.length-1? curSum+maxProfixStep(prices, index):curSum;
    }

    /**
     * 展平二叉搜索树
     * @param root
     * @return
     */
    public TreeNode increasingBST(TreeNode root) {
        if(root == null) {
            return null;
        }
        TreeNode left = increasingBST(root.left);

        if (left != null) {
            left.right = root;
            root.left = null;
        }

        TreeNode right = increasingBST(root.right);

        if (right != null) {
            root.right = right;
        }
        return root;
    }


    /**
     * 51 节点之和的最大路径  困难 ，真的难
     * @param root
     * @return
     */
    public static int max = Integer.MIN_VALUE;


    public int maxPathSum(TreeNode root) {
        if(root == null) {
            return max;
        }
        maxPathSum(root.left);
        maxPathSumChild(root, 0);
        maxPathSum(root.right);
        return max;
    }

    private int maxPathSumChild(TreeNode root, int sum) {
        sum += root.val;
        max = Math.max(max, sum);
        maxPathSumChild(root.left, sum);
        maxPathSumChild(root.right, sum);
        return 0;
    }

    /**
     * 50 向下的路径节点之和
     * @param root
     * @param targetSum
     * @return
     */
    public int pathSum(TreeNode root, int targetSum) {
        if(root == null) {
            return 0;
        }
        int cur = 0;
        if(root.val == targetSum) {
            cur = 1;
        }
        return cur + pathSum(root.left, targetSum) + pathSum(root.right, targetSum)
                + pathSum(root.left, targetSum-root.val) + pathSum(root.right, targetSum - root.val);
    }


    /**
     * 49 从根节点到叶子节点路径之和
     * @param root
     * @return
     */
    public int sumNumbers(TreeNode root) {
        int result = root.val;
        if(root.left == null && root.right == null) {
            return result;
        }
        return sumNumbersChild(root.left, result*10) + sumNumbersChild(root.right, result*10);
    }

    private int sumNumbersChild(TreeNode root, int parent) {
        if(root == null) {
            return 0;
        }
        int cur = parent + root.val;
        if(root.left == null && root.right == null) {
            return cur;
        }
        return sumNumbersChild(root.left, cur*10) + sumNumbersChild(root.right, cur*10);
    }


    /**
     * 47 二叉树剪枝
     */
    public TreeNode pruneTree(TreeNode root) {
        if(root == null) {
            return null;
        }

        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);

        if(root.left == null && root.right == null && root.val == 0) {
            return null;
        }
        return root;
    }

    /**
     * 46 二叉树的右侧视图
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null) {
            return result;
        }
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        while (list.size()>0) {
            int size = list.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = list.poll();
                if(cur.left!=null) {
                    list.add(cur.left);
                }
                if(cur.right!=null) {
                    list.add(cur.right);
                }
                if(i == size-1) {
                    result.add(cur.val);
                }
            }
        }
        return result;
    }

    /**
     * 45 二叉树最底层最左边的值
     * @param root
     * @return
     */
    public int findBottomLeftValue(TreeNode root) {
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        int result = -1;
        while (list.size()>0) {
            int size = list.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = list.poll();
                if(cur.left!=null) {
                    list.add(cur.left);
                }
                if(cur.right!=null) {
                    list.add(cur.right);
                }
                if(i == 0) {
                    result = cur.val;
                }
            }
        }
        return result;
    }


    public boolean findTarget(TreeNode root, int target) {
        if(root == null) {
            return false;
        }
        if(root.left == null && root.right == null) {
            return root.val == target;
        }
        return findTarget(root.left, target-root.val) || findTarget(root.right, target-root.val);
    }

    /**
     * 二叉树非递归遍历
     */
    public void inOrderWithoutRecur(TreeNode root) {
        //1、借助栈结构
        //2、
        if(root == null) {
            return;
        }
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root;

        while (!s.isEmpty() || cur!=null) {

            while (cur != null) {
                s.add(cur);
                cur = cur.left;
            }

            if (!s.isEmpty()) {
                TreeNode pop = s.pop();
                System.out.println(pop.val);
                if(pop.right != null) {
                    cur = pop.right;
                }
            }
        }
    }

    /**
     * 102 二叉树的层序遍历
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) {
            return new ArrayList<>();
        }

        List<List<Integer>> result = new ArrayList<>();
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);

        while (list.size()>0) {
            int size = list.size();
            List<Integer> curList = new ArrayList<>(size);
            for (int i = 0; i < size; i++) {
                TreeNode cur = list.poll();
                if(cur.left!=null) {
                    list.add(cur.left);
                }
                if(cur.right!=null) {
                    list.add(cur.right);
                }
                curList.add(cur.val);
            }
            result.add(curList);
        }
        return result;
    }

    //8 字符串转整数
    public int myAtoi(String s) {
        //1、截断前面的空格
        //2、判断是否为数字
        //3、判断是否在整数范围内
        if(s.length()==0) {return 0;}

        long result = 0;
        StringBuilder sb = new StringBuilder();

        s = s.trim();
        int less = 1;
        boolean fuhao = false;

        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            if(cur == '-' && !fuhao && sb.length()==0) {
                less = -1;
                fuhao = true;
                continue;
            }
            if(cur == '+' && !fuhao && sb.length()==0) {
                fuhao = true;
                continue;
            }
            if(!Character.isDigit(cur)) {
                break;
            }
            sb.append(cur);

            if(sb.length()>0) {
                result = Long.parseLong(sb.toString())*less;
            }

            if(result>Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            }
            if(result<Integer.MIN_VALUE) {
                return Integer.MIN_VALUE;
            }
        }
        return (int)result;
    }

    //7 反转整数
    public int reverse(int x) {
        String xStr = x+"";

        int less = 1;
        if(x<0) {
            xStr = xStr.substring(1);
            less = -1;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < xStr.length(); i++) {
            sb.append(xStr.charAt(i));
        }
        long reverse = less * Long.parseLong(sb.reverse().toString());

        if(reverse > Integer.MAX_VALUE || reverse<Integer.MIN_VALUE) {
            return 0;
        }
        return (int)reverse;

    }

    //5 最长回文串
    public String longestPalindrome(String s) {
        if(s.length()<=1) {
            return s;
        }

        boolean[][] arr = new boolean[s.length()-1][s.length()-1];

        for (int i = 0; i < s.length(); i++) {
            arr[i][1] = true;
        }

        for (int i = 0; i < s.length(); i++) {
            for (int len = 2; len < s.length()-i+1; len++) {

            }
        }
        return "";
    }

    //2 两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int add = 0;
        ListNode result = new ListNode(-1);
        ListNode head = result;
        while (l1!=null || l2!= null) {
            int a = l1 == null? 0 : l1.val;
            int b = l2 == null? 0 : l2.val;
            int sum = a+b+add;

            head.next = new ListNode(sum%10);
            add = sum/10;

            if(l1!=null) {
                l1 = l1.next;
            }
            if(l2!=null) {
                l2 = l2.next;
            }
            head = head.next;
        }

        if(add>0) {
            head.next =new ListNode(add);
        }

        return result.next;
    }

    /**
     * 主站 121 股票买卖的最佳时机
     * @param prices
     * @return
     */
    public int maxProfitEasy(int[] prices) {
        return 0;
    }
}
